//
// Created by gushen610140 on 2024/5/1.
//

#ifndef DATASTRUCTURECOURSE_GDISJOINTSET_H
#define DATASTRUCTURECOURSE_GDISJOINTSET_H


class GDisjointSet {
private:
    int *_parent;
    int *_rank;
    int _size;
public:
    GDisjointSet(int size) {
        _parent = new int[size];
        _rank = new int[size]();
        _size = size;
        for (int i = 0; i < size; i++) {
            _parent[i] = i;
        }
    }

    int find(int x) {
        // 路径压缩
        if (_parent[x] != x) {
            _parent[x] = find(_parent[x]);
        }
        return _parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        // 已经在同一个集合中
        if (rootX == rootY) {
            return;
        }
        // 将低级别的集合合并到高级别的集合中
        if (_rank[rootX] < _rank[rootY]) {
            _parent[rootX] = rootY;
        } else if (_rank[rootX] > _rank[rootY]) {
            _parent[rootY] = rootX;
        } else {
            // 同级别的集合，合并后级别加一
            _parent[rootY] = rootX;
            _rank[rootX]++;
        }
    }

    int getSize() const {
        return _size;
    }
};


#endif //DATASTRUCTURECOURSE_GDISJOINTSET_H
